package test;

//分割数组的最大值: https://leetcode.cn/problems/split-array-largest-sum/description/
//时间复杂度: O(n*log(sum))
public class SplitArray {
	//f的功能： 让nums的每部分的累加和均<=limit，可以划分为几部分
    public int f(int[] nums,long limit){
        int parts=1;
        long sum=0;
        for(int x:nums){
            if(x>limit)  //如果nums[i]>limit，一定无法划分乘累加和<=limit
                return Integer.MAX_VALUE;
            else if(sum+x>limit){ //达标就进行1次划分
                parts++;
                sum=x;
            }
            else if(sum+x<=limit){
                sum+=x;
            }
        }
        return parts;
    }
    public int splitArray(int[] nums, int k) {
        long sum=0,ans=0;
        //答案的范围[0,sum]
        for(int x:nums){
            sum+=x;
        }
        long l=0,r=sum;
        while(l<=r){
            long mid=l+(r-l)/2;
            if(f(nums,mid)<=k){
                ans=mid;
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        return (int)ans;
    }
}
